//
// Created by Administrator on 2021/5/20.
//

//在一个 N x N 的坐标方格grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
//
//现在开始下雨了。当时间为t时，此时雨水导致水池中任意位置的水位为t。
// 你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。
// 假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。
//
//你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台(N-1, N-1)？
#include <vector>
#include <iostream>
#include <unordered_set>
#include <queue>

using namespace std;

class Solution { // dfs
    vector<pair<int, int>> delta{{1,  0},
                                 {-1, 0},
                                 {0,  1},
                                 {0,  -1}};
public:
    int swimInWater(vector<vector<int>> &grid) {
        int N = (int) grid.size();
        int lhs = max(grid[0][0], grid[N - 1][N - 1]);
        int rhs = N * N - 1;
        while (lhs < rhs) {
            int mid = (lhs + rhs) / 2;
            vector<vector<bool>> seen(N, vector<bool>(N, false)); // 每次用一个新的地图
            if (dfs(grid, seen, 0, 0, mid, N)) rhs = mid;
            else lhs = mid + 1;
        }
        return lhs;
    }

    bool dfs(vector<vector<int>> &grid, vector<vector<bool>> &seen, int x, int y, int t, int N) {
        // 检查在t时刻，是否有一条从0,0 到达N-1,N-1的路径
        seen[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            // 四周有没有可以游动的网格
            int newX = x + delta[i].first;
            int newY = y + delta[i].second;
            if (check(newX, newY, N) and !seen[newX][newY] and grid[newX][newY] <= t) {
                if (newX == N - 1 and newY == N - 1) return true;
                if (dfs(grid, seen, newX, newY, t, N)) return true;
            }
        }
        return false;
    }

    bool check(int x, int y, int N) {
        // 检查某个点是否在格子内
        return x >= 0 and x < N and y >= 0 and y < N;
    }

};

class Solution2 { // bfs
    vector<pair<int, int>> delta{{1,  0},
                                 {-1, 0},
                                 {0,  1},
                                 {0,  -1}};
public:
    int swimInWater(vector<vector<int>> &grid) {
        int N = (int) grid.size();
        int lhs = max(grid[0][0], grid[N - 1][N - 1]);
        int rhs = N * N - 1;
        while (lhs < rhs) {
            int mid = (lhs + rhs) / 2;
            if (bfs(grid, mid, N)) rhs = mid;
            else lhs = mid + 1;
        }
        return lhs;
    }

    bool bfs(vector<vector<int>> &grid, int t, int N) {
        // 检查在t时刻，是否有一条从0,0 到达N-1,N-1的路径
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        vector<vector<bool>> seen(N, vector<bool>(N, false));
        seen[0][0] = true;
        while (!q.empty()) {
            auto front = q.front();
            q.pop();
            int x = front.first;
            int y = front.second;
            for (int i = 0; i < 4; ++i) {
                int newX = x + delta[i].first;
                int newY = y + delta[i].second;
                if (inArea(newX, newY, N) && !seen[newX][newY] && grid[newX][newY] <= t) {
                    if (newX == N - 1 && newY == N - 1) return true;
                    q.emplace(newX, newY);
                    seen[newX][newY] = true;
                }
            }
        }
        return false;
    }

    bool inArea(int x, int y, int N) {
        // 检查某个点是否在格子内
        return x >= 0 and x < N and y >= 0 and y < N;
    }

};

class UnionSet {
private:
    vector<int> parent;

public:
    UnionSet(int n) {
        parent.reserve(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    bool Merge(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (x == y) {
            return false;
        }
        parent[x] = y;
        return true;
    }

    bool Connected(int x, int y) {
        return Find(x) == Find(y);
    }
};

class Solution3 { // 并查集
public:
    int swimInWater(vector<vector<int>> &grid) {
        int N = (int) grid.size();
        int n = N * N;
        // 按照grid高度从小到大排列，高度 对应 一维表示的位置
        vector<int> index(n);
        // index的里按照高度从小到大排列
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                index[grid[i][j]] = i * N + j;
            }
        }

        UnionSet us(n);

        vector<int> dir{1, 0, -1, 0, 1};
        // 这里i对应index编号，但它也正好是对应的时间
        for (int i = 0; i < n; ++i) {
            int x = index[i] / N;
            int y = index[i] % N;
            for (int j = 0; j < 4; ++j) {
                // i高度（时间）的那个点四周是否有连通集
                int nx = x + dir[j];
                int ny = y + dir[j + 1];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[nx][ny] <= i) {
                    if (us.Merge(nx * N + ny, index[i])) {
                        // 最终结果就是希望 n-1和0连通
                        if (us.Connected(n - 1, 0)) {
                            return i;
                        }
                    }
                }
            }
        }

        return -1;
    }
};


int main() {
    vector<vector<int>> m{{0,  1,  2,  3,  4},
                          {24, 23, 22, 21, 5},
                          {12, 13, 14, 15, 16},
                          {11, 17, 18, 19, 20},
                          {10, 9,  8,  7,  6}};
    vector<vector<int>> n{{0, 2},
                          {1, 3}};
    Solution3 sol;
    cout << sol.swimInWater(m) << endl;
    cout << sol.swimInWater(n) << endl;
    return 0;
}

